﻿//【进阶】34.哈希
//【头文件包含】
//C++的主要头文件
#include<iostream>//c++的输入输出流
using namespace std;
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
//C的主要头文件
//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
//#include<string.h> 
#include"MySet.h"
#include"MyMap.h"
#include"HashTable.h"




//【命名空间】

//【结构体声明】【类声明】
//【函数声明】
void Test1();void Test2();void Test3();


//【主函数】
int main()
{
	//Test1();
	Test2();
	Test3();


	cout << "****主函数结束****" << endl;
	return 0;
}

//【函数定义】


/*测试用例*/void Test1()
{
	cout << "****测试用例开始****"<< endl;
	myspace::TestMyMap1();
	myspace::TestMySet1();
	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test2()
{
	cout << "****测试用例开始****" << endl;
	unordered_set<int> us;
	us.insert(4);
	us.insert(2);
	us.insert(1);
	us.insert(5);
	us.insert(6);
	unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	unordered_map<string,int> um;
	um.insert(make_pair("find", 1));
	um.insert(make_pair("my", 2));
	um.insert(make_pair("soul", 3));
	um.insert(make_pair("cool",4));
	unordered_map<string, int>::iterator it2 = um.begin();
	while (it2 != um.end())
	{
		cout << it2->first <<":"<<it2->second << " ";
		++it2;
	}
	cout << endl;
	cout << "****测试用例结束****" << endl<<endl;
}

/*测试用例*/void Test3()
{
	cout << "****测试用例开始****" << endl;

	cout << "****测试用例结束****" << endl << endl;
}




//【笔记】
//【进阶】33.模拟实现map、set
	// map还有重载[] 返回的是插入或查找点的pair的value
//【进阶】34.哈希
	// unordered_map   unordered_set  （无序的map和set/底层是哈希实现的）
		// 用法和map、set基本一致，但不支持排序，unordered只支持单向迭代器,构建对象可以增、删、查、不可改
	//map、set与unordered_map   unordered_set区别和联系
		// 1.都支持key、key/value搜索场景，且功能使用基本一样
		// 2.map、set底层使用红黑树实现，增删查时间复杂度O（log_2_N） 
		// 3.unordered底层使用哈希实现，增删查时间复杂度O（1）
		// 4.遍历前者有序，迭代器双向，后者无序，单向迭代器
	//海量数据下利用哈希查找效率更高
	//哈希的概念
		//哈希是一种映射的对应关系：在排序中提到的计数排序也是利用了一种映射关系
		// 映射
			// 1.直接定值法：映射只跟关键字直接或间接相关（是一种相对映射）
			// 2.除留余数法：取key%10的结果建立映射关系
		//插入元素
			// 根据待插入元素的关键码，计算出该元素的存储位置并按此位置进行存放
		//搜索元素
			// 对元素的关键码进行相同计算，得到元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
		//哈希的这种映射关系也叫散列 
		//但是
			// 哈希表如果两个值计算出结果相同，会出现哈希冲突，需要用一些方法进行处理
		//解决冲突的方法
			// 闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，把key存放到冲突位置中的“下一个”空位置中去。
			//1. 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。//插入时，找到不冲突位置插入，删除时，采用伪删除进行标记
			//如果哈希表越满越容易发生冲突，冲突越多，效率越低 
		









